10.3 KB · ⇊ 7 parts · ⤓ Micron 10.3 KB · ⤓ HTML 39.0 KB

top

In mathematics, a symmetric Boolean function is a Boolean function whose value does not depend on the order of its input bits, i.e., it depends only on the number of ones (or zeros) in the input.cite-ref-weg-1-0[1] For this reason they are also known as Boolean counting functions.cite-ref-2[2]

There are 2n+1 symmetric n-ary Boolean functions. Instead of the truth table, traditionally used to represent Boolean functions, one may use a more compact representation for an n-variable symmetric Boolean function: the (n + 1)-vector, whose i-th entry (i = 0, ..., n) is the value of the function on an input vector with i ones. Mathematically, the symmetric Boolean functions correspond one-to-one with the functions that map n+1 elements to two elements, f : { 0 , 1 , . . . , n } → → { 0 , 1 } {\displaystyle f:\{0,1,...,n\}\rightarrow \{0,1\}} .

Symmetric Boolean functions are used to classify Boolean satisfiability problems.

• Special cases

• Properties

• Weight

• Algebraic normal form

• Unit hypercube polynomial

• Examples

• See also

• References

A number of special cases are recognized:cite-ref-weg-1-1[1]

• Majority function: their value is 1 on input vectors with more than n/2 ones

• Threshold functions: their value is 1 on input vectors with k or more ones for a fixed k

• All-equal and not-all-equal function: their values is 1 when the inputs do (not) all have the same value

• Exact-count functions: their value is 1 on input vectors with k ones for a fixed k

• One-hot or 1-in-n function: their value is 1 on input vectors with exactly one one

• One-cold function: their value is 1 on input vectors with exactly one zero

• Congruence functions: their value is 1 on input vectors with the number of ones congruent to k mod m for fixed k, m

• Parity function: their value is 1 if the input vector has odd number of ones

The n-ary versions of AND, OR, XOR, NAND, NOR and XNOR are also symmetric Boolean functions.

In the following, f k {\displaystyle f_{k}} denotes the value of the function f : { 0 , 1 } n → → { 0 , 1 } {\displaystyle f:\{0,1\}^{n}\rightarrow \{0,1\}} when applied to an input vector of weight k {\displaystyle k} .

The weight of the function can be calculated from its value vector:

| f | = ∑ ∑ k = 0 n ( n k ) f k {\displaystyle |f|=\sum _{k=0}^{n}{\binom {n}{k}}f_{k}}

The algebraic normal form either contains all monomials of certain order m {\displaystyle m} , or none of them; i.e. the Möbius transform f ^ ^ {\displaystyle {\hat {f}}} of the function is also a symmetric function. It can thus also be described by a simple (n+1) bit vector, the ANF vector f ^ ^ m {\displaystyle {\hat {f}}_{m}} . The ANF and value vectors are related by a Möbius relation: f ^ ^ m = ⨁ ⨁ k 2 ⊆ ⊆ m 2 f k {\displaystyle {\hat {f}}_{m}=\bigoplus _{k_{2}\subseteq m_{2}}f_{k}} where k 2 ⊆ ⊆ m 2 {\displaystyle k_{2}\subseteq m_{2}} denotes all the weights k whose base-2 representation is covered by the base-2 representation of m (a consequence of Lucas’ theorem).cite-ref-3[3] Effectively, an n-variable symmetric Boolean function corresponds to a log(n)-variable ordinary Boolean function acting on the base-2 representation of the input weight.

For example, for three-variable functions:

f ^ ^ 0 = f 0 f ^ ^ 1 = f 0 ⊕ ⊕ f 1 f ^ ^ 2 = f 0 ⊕ ⊕ f 2 f ^ ^ 3 = f 0 ⊕ ⊕ f 1 ⊕ ⊕ f 2 ⊕ ⊕ f 3 {\displaystyle {\begin{array}{lcl}{\hat {f}}_{0}&=&f_{0}\\{\hat {f}}_{1}&=&f_{0}\oplus f_{1}\\{\hat {f}}_{2}&=&f_{0}\oplus f_{2}\\{\hat {f}}_{3}&=&f_{0}\oplus f_{1}\oplus f_{2}\oplus f_{3}\end{array}}}

So the three variable majority function with value vector (0, 0, 1, 1) has ANF vector (0, 0, 1, 0), i.e.: Maj ( x , y , z ) = x y ⊕ ⊕ x z ⊕ ⊕ y z {\displaystyle {\text{Maj}}(x,y,z)=xy\oplus xz\oplus yz}

The coefficients of the real polynomial agreeing with the function on { 0 , 1 } n {\displaystyle \{0,1\}^{n}} are given by: f m ∗ ∗ = ∑ ∑ k = 0 m ( − − 1 ) | k | + | m | ( m k ) f k {\displaystyle f_{m}^{*}=\sum _{k=0}^{m}(-1)^{|k|+|m|}{\binom {m}{k}}f_{k}} For example, the three variable majority function polynomial has coefficients (0, 0, 1, -2): Maj ( x , y , z ) = ( x y + x z + y z ) − − 2 ( x y z ) {\displaystyle {\text{Maj}}(x,y,z)=(xy+xz+yz)-2(xyz)}

| Function value | Function value | Function value | Function value | Value vector | Weight | Name | Colloquial description | ANF vector |

|---|---|---|---|---|---|---|---|---|

| 0 | 1 | 2 | 3 | Value vector | Weight | Name | Colloquial description | ANF vector |

| F | F | F | F | (0, 0, 0, 0) | 0 | Constant false | "never" | (0, 0, 0, 0) |

| F | F | F | T | (0, 0, 0, 1) | 1 | Three-way AND , Threshold(3), Count(3) | "all three" | (0, 0, 0, 1) |

| F | F | T | F | (0, 0, 1, 0) | 3 | Count(2), One-cold | "exactly two" | (0, 0, 1, 1) |

| F | F | T | T | (0, 0, 1, 1) | 4 | Majority, Threshold(2) | "most", "at least two" | (0, 0, 1, 0) |

| F | T | F | F | (0, 1, 0, 0) | 3 | Count(1), One-hot | "exactly one" | (0, 1, 0, 1) |

| F | T | F | T | (0, 1, 0, 1) | 4 | Three-way XOR , (odd) parity | "one or three" | (0, 1, 0, 0) |

| F | T | T | F | (0, 1, 1, 0) | 6 | Not-all-equal | "one or two" | (0, 1, 1, 0) |

| F | T | T | T | (0, 1, 1, 1) | 7 | Three-way OR , Threshold(1) | "any", "at least one" | (0, 1, 1, 1) |

| T | F | F | F | (1, 0, 0, 0) | 1 | Three-way NOR , Count(0) | "none" | (1, 1, 1, 1) |

| T | F | F | T | (1, 0, 0, 1) | 2 | All-equal | "all or none" | (1, 1, 1, 0) |

| T | F | T | F | (1, 0, 1, 0) | 4 | Three-way XNOR , even parity | "none or two" | (1, 1, 0, 0) |

| T | F | T | T | (1, 0, 1, 1) | 5 | | "not exactly one" | (1, 1, 0, 1) |

| T | T | F | F | (1, 1, 0, 0) | 4 | ( Horn clause ) | "at most one" | (1, 0, 1, 0) |

| T | T | F | T | (1, 1, 0, 1) | 5 | | "not exactly two" | (1, 0, 1, 1) |

| T | T | T | F | (1, 1, 1, 0) | 7 | Three-way NAND | "at most two" | (1, 0, 0, 1) |

| T | T | T | T | (1, 1, 1, 1) | 8 | Constant true | "always" | (1, 0, 0, 0) |

• Symmetric function

cite-note-weg-11. ↑ Ingo Wegener, "The Complexity of Symmetric Boolean Functions", in: Computation Theory and Logic, Lecture Notes in Computer Science, vol. 270, 1987, pp. 433–442

cite-note-22. ↑ "BooleanCountingFunction—Wolfram Language Documentation". reference.wolfram.com. Retrieved 2021-05-25.

cite-note-33. ↑ citerefcanteautvideau2005Canteaut, A.; Videau, M. (2005). "Symmetric Boolean functions". IEEE Transactions on Information Theory. 51 (8): 2791–2811. doi:10.1109/TIT.2005.851743. ISSN 1557-9654.